package com.cheung.leetcode.tree;

import lyroot.entity.TreeNode;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.tree
 * @Author :  cheungming
 * @CreateTime : 2024-05-15 11:23:07
 * @Description : 中序遍历
 * @Version : 1.0
 */
public class Code94Test {

    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> list = new ArrayList<>();
        search(root, list);
        return list;
    }

    public void search(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        // 中序遍历，左根右
        search(node.left, list);
        list.add(node.val);
        search(node.right, list);
    }

    @Test
    public void test1() {
        TreeNode root = new TreeNode(1);

        TreeNode node2 = new TreeNode(2);
        root.right = node2;

        node2.left = new TreeNode(3);

        assert Objects.equals(List.of(1, 3, 2), inorderTraversal(root));
    }

    @Test
    public void test2() {
        assert Objects.equals(List.of(), inorderTraversal(null));
    }

    @Test
    public void test3() {
        assert Objects.equals(List.of(1), inorderTraversal(new TreeNode(1)));
    }

}
